ALGORITHM is a procedure for solving a mathematical problem
(as of finding the greatest common divisor) in a finite number of steps that
frequently involves repetition of an operation; broadly : a step-by-step procedure
for solving a problem or accomplishing some end.
It can be understood by taking an example of cooking a new recipe.
To cook a new recipe, one reads the instructions and steps and execute them one by one, in the given sequence.
The result thus obtained is the new dish cooked perfectly. Similarly, algorithms help to do a task in programming to get the expected output.
The Algorithm designed are language-independent, i.e. they are just plain instructions that can be implemented in any language,
and yet the output will be the same, as expected.
It can be understood by taking an example of cooking a new recipe. To cook a new recipe, one reads the instructions and steps and execute them one by one, in the given sequence. The result thus obtained is the new dish cooked perfectly. Every time you use your phone, computer, laptop, or a calculator you are using Algorithms. Similarly, algorithms help to do a task in programming to get the expected output. The Algorithm designed are language-independent, i.e. they are just plain instructions that can be implemented in any language, and yet the output will be the same, as expected.
As one would not follow any written instructions to cook the recipe, but only the standard one. Similarly, not all written instructions for programming
is an algorithm. In order for some instructions to be an algorithm, it must have the following characteristics:
1. Clear and Unambiguous:
Algorithm should be clear and unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
2. Well-Defined Inputs:
If an algorithm says to take inputs, it should be well-defined inputs.
3. Well-Defined Outputs:
The algorithm must clearly define what output will be yielded and it should be well-defined as well.
4. Finite-ness:
The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
5. Feasible:
The algorithm must be simple, generic and practical, such that it can be executed upon with the available resources. It must not contain some future technology,
or anything.
6. Language Independent:
The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will
be same, as expected.
The simplest possible algorithm that can be devised to solve a problem is called the brute force algorithm. To device an optimal solution first we need to get a solution at least and then try to optimise it. Every problem can be solved by brute force approach although generally not with appreciable space and time complexity.
In this algorithm, a decision is made that is good at that point without considering the future. This means that some local best is chosen and considers it as the global optimal. There are two properties in this algorithm. Greedily choosing the best option Optimal substructure property: If an optimal solution can be found by retrieving the optimal solution to its subproblems. Greedy Algorithm does not always work but when it does, it works like a charm! This algorithm is easy to device and most of the time the simplest one. But making locally best decisions does not always work as it sounds. So, it is replaced by a reliable solution called Dynamic Programming approach.
This is one of the simplest to devise algorithms as it does not require specifically think about every subproblem. This means we just need to think about the existing cases and the solution of the simplest subproblem, all other complexity will be handled by it automatically. Recursion is a very powerful tool although we should always take care of memory management here as recursion works using recursive stack which is called every time recursion function is invoked. Recursion simply means calling itself to solve its subproblems.
It is an improvement to the brute force approach. Here we start with one possible option out of many available and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other and try to solve it. It is a form of recursion, it’s just that when a given option cannot give a solution, we backtrack to the previous option which can give a solution, and proceed with other options.
Algorithms of this type are also known as memoization techniques. As a result, the thought is to keep track of the recently determined result to avoid calculating it over and over again. Using Dynamic Programming, you can break up the unpredictable issue into smaller, more manageable subproblems and put the outcome aside for later. We can say that it remembers previous results and uses them to find new ones. it is the third main types of algorithms.
With the Divide and Conquer algorithm, the aim is to tackle the issue in two sections, the first of which divides the problem into subproblems that are similar in nature. Second, we will approach the more modest issue autonomously and then add the combined outcome to complete our final response.
Time Factor:
Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
Time Complexity: Time complexity of an algorithm refers to the amount of time that this algorithm requires to execute and get the result.
This can be for normal operations, conditional if-else statements, loop statements, etc.
How to calculate Time Complexity?
The time complexity of an algorithm is also calculated by determining following 2 components:
Constant time part: Any instruction that is executed just once comes in this part. For example, input, output, if-else, switch, etc.
Variable Time Part: Any instruction that is executed more than once, say n times, comes in this part. For example, loops, recursion, etc.
Space Factor:
Space is measured by counting the maximum memory space required by the algorithm.
Space Complexity: Space complexity of an algorithm refers to the amount of memory that this algorithm requires to execute and get the result.
This can be for inputs, temporary operations, or outputs.
How to calculate Space Complexity?
The space complexity of an algorithm is calculated by determining following 2 components:
Fixed Part: This refers to the space that is definitely required by the algorithm. For example,
input variables, output variables, program size, etc.
Variable Part: This refers to the space that can be different based on the implementation of the algorithm.
For example, temporary variables, dynamic memory allocation, recursion stack space, etc.
It should terminate after finite time.
It should produce at least one output.
It should take zero or more input.
It should be deterministic means giving same output for same input case.
Every step in algorithm must be effective i.e. every step should do some work.
It is easy to understand.
Algorithm is a step-wise representation of a solution to a given problem.
In Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.
Writing an algorithm takes a long time so it is time-consuming.
Understanding complex logic through algorithms can be very difficult.
Branching and Looping statements are difficult to show in Algorithms(imp).
Home
Searching Introduction
